/**
* @description: 866. 回文素数
* @author hewei
* @date 2022/9/16 14:16
* @version 1.0
*/

public class PrimePalindrome {

    public static void main(String[] args) {
        PrimePalindrome primePalindrome = new PrimePalindrome();
        System.out.println(primePalindrome.primePalindrome(13));
    }

    public int primePalindrome(int n) {
        while (true) {
            n = nextNum(n);
            if (check(n)) return n;
            ++n;
        }
    }

    public int nextNum(int i) {
        char[] chars = String.valueOf(i).toCharArray();
        int n = chars.length;
        while (true) {
            for (int j = 0; j < n / 2; j++) {
                chars[n - 1 - j] = chars[j];
            }
            if (Integer.parseInt(String.valueOf(chars)) < i) {
                int temp = n % 2 == 0 ? n / 2 - 1 : n / 2;
                while (chars[temp] == '9') {
                    chars[temp--] = '0';
                }
                chars[temp]++;
            } else return Integer.parseInt(String.valueOf(chars));
        }
    }

    public boolean check(int i) {
        if (i == 1) return false;
        if (i == 2) return true;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) return false;
        }
        return true;
    }
}
